package com.future;

import com.future.util.TreeNode;

import java.util.Stack;

/**
 * Description:
 * 给定一个整数数组，它表示BST(即 二叉搜索树 )的 先序遍历 ，构造树并返回其根。
 * <p>
 * 保证 对于给定的测试用例，总是有可能找到具有给定需求的二叉搜索树。
 * <p>
 * 二叉搜索树 是一棵二叉树，其中每个节点， Node.left 的任何后代的值 严格小于 Node.val , Node.right 的任何后代的值 严格大于 Node.val。
 * <p>
 * 二叉树的 前序遍历 首先显示节点的值，然后遍历Node.left，最后遍历Node.right。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/construct-binary-search-tree-from-preorder-traversal
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @Author: future
 * @Date:2022/3/26:21:50
 */
public class Solution_1008 {

    public static void main(String[] arr) {
        int[] preorder = {8, 5, 1, 7, 10, 12};
        TreeNode treeNode = bstFromPreorder(preorder);
        TreeNode treeNode2 = bstFromPreorder_v2(preorder);
        printPreTree(treeNode);
        System.out.println();
        printPreTree(treeNode2);
    }

    /**
     * 单调栈
     *
     * @param preorder
     * @return
     */
    public static TreeNode bstFromPreorder_v2(int[] preorder) {
        if (preorder == null || preorder.length == 0) {
            return null;
        }
        int N = preorder.length;
        int[] monotonicStack = new int[N];
        for (int i = 0; i < N; i++) {
            monotonicStack[i] = -1;
        }
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < N; i++) {
            while (!stack.isEmpty() && preorder[stack.peek()] < preorder[i]) {
                monotonicStack[stack.pop()] = i;
            }
            stack.add(i);
        }
        return process_v2(preorder, monotonicStack, 0, preorder.length - 1);
    }


    private static TreeNode process_v2(int[] preorder, int[] monotonicStack, int L, int R) {
        if (L > R) {
            return null;
        }
        /**
         * 知道第一个大于L位置的下标
         */
        TreeNode head = new TreeNode(preorder[L]);
        int firstBig = monotonicStack[L] == -1 ? R + 1 : monotonicStack[L];
        // 递归左边
        head.left = process_v2(preorder, monotonicStack, L + 1, firstBig - 1);
        // 递归右边
        head.right = process_v2(preorder, monotonicStack, firstBig, R);
        return head;
    }

    /**
     * 递归
     *
     * @param preorder
     * @return
     */
    public static TreeNode bstFromPreorder(int[] preorder) {
        if (preorder == null || preorder.length == 0) {
            return null;
        }
        return process(preorder, 0, preorder.length - 1);
    }

    private static TreeNode process(int[] preorder, int L, int R) {
        if (L > R) {
            return null;
        }
        /**
         * 知道第一个大于L位置的下标
         */
        int firstBig = L + 1;
        for (; firstBig <= R; firstBig++) {
            if (preorder[firstBig] > preorder[L]) {
                break;
            }
        }
        TreeNode head = new TreeNode(preorder[L]);
        // 递归左边
        head.left = process(preorder, L + 1, firstBig - 1);
        // 递归右边
        head.right = process(preorder, firstBig, R);
        return head;
    }

    private static void printPreTree(TreeNode head) {
        if (head == null) {
            return;
        }
        printProcess(head);
    }

    private static void printProcess(TreeNode head) {
        if (head == null) {
            return;
        }
        System.out.print(" " + head.val);
        printPreTree(head.left);
        printPreTree(head.right);
    }
}
